package leetcode.editor.cn.dsa08_hashtable;
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

public class LongestSubstringWithoutRepeatingCharacters3_3 {
    public static void main(String[] args) {
        LongestSubstringWithoutRepeatingCharacters3_3.Solution solution =
                new LongestSubstringWithoutRepeatingCharacters3_3().new Solution();
        System.out.println(solution.lengthOfLongestSubstring("abcabcbb")); //3
        System.out.println(solution.lengthOfLongestSubstring("dvdf")); //3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb")); //1
        System.out.println(solution.lengthOfLongestSubstring("pwwkew")); //3
        System.out.println(solution.lengthOfLongestSubstring("")); //0
        System.out.println(solution.lengthOfLongestSubstring("abcdefg")); //7
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 最优解：哈希表 + 双指针
         * 思路：
         *    遍历字符串的所有字符，使用双指针定位不重复子串的起止索引，
         *    并将字符临时记录到哈希表中，每次计算子串的长度并统计最大值
         * 步骤：
         * 1.定义哈希表，临时存储子串字符和查重
         *   定义哈希函数，对任意字符生成唯一整数值
         * 2.遍历字符串，通过双指针循环定位子串
         *   右指针在哈希表中是否存在：
         *   否，记录到哈希表，移动右指针，计算长度；
         *   是，删除哈希表中左指针元素，移动左指针，重复检查右指针元素是否还存在；
         * 3.每次计算子串长度，比较并保留最大值
         * 细节问题：
         *   子串长度是：end + 1 - start
         *   出现重复元素后，左指针逐个移动，直到与当前重复的字符索引+1
         *
         * @param s
         * @return
         */
        public int lengthOfLongestSubstring(String s) {
            int len; // 源字符串长度
            if (s == null || (len = s.length()) == 0) {
                return 0;
            }
            int res = 0, // 最长不重复子串的长度
                left = 0, // 子串最左端字符索引
                right = 0; // 子串最右端字符索引

            // 1.定义哈希表，支持ASCII码表的全部字符
            char[] chars = new char[128];
            // 2.遍历字符串的所有字符
            while (right < len) {
                char rightChar = s.charAt(right); // 右指针字符
                // 相当于将hash值 % 128
                char c = chars[(chars.length - 1) & hash(rightChar)]; // hash算法
                if (rightChar != c) { // 未重复出现，也可以用判空
                    // 2.1.双指针定位子串索引：右指针自增
                    right++;
                    // 将不重复字符记录到哈希表中
                    chars[(chars.length - 1) & hash(rightChar)] = rightChar;
                    // 3.每次记录子串长度，并计算最大值
                    int size = right - left; // 每个不重复子串的长度
                    res = res > size ? res : size;
                } else {  // 重复出现
                    // 2.2.双指针定位子串索引：左指针自增。从哈希表中移出最左侧字符：赋默认值
                    char leftChar = s.charAt(left++);
                    chars[(chars.length - 1) & hash(leftChar)] = '\u0000';
                    // 此时right不能+1，因为需要重复检查左指针元素
                }
            }
            return res;
        }

        /**
         * 哈希算法
         * 根据给定字符计算出一个 int 型哈希值
         */
        int hash(char key) {
            return key;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}